package class03;

public class Code01_KMP {

	// 实际上getindexOf并不是KMP
	public static int getIndexOf(String s, String m) {
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		char[] str1 = s.toCharArray();
		char[] str2 = m.toCharArray();
		int i1 = 0; // i1是主串中要比对的位置
		int i2 = 0; // i2是子串中要比对的位置
		int[] next = getNextArray(str2); // O(M)

		// O(N)
		while (i1 < str1.length && i2 < str2.length) {
			if (str1[i1] == str2[i2]) { // i1与i2所指向的字符相同，则继续比较后继字符
				i1++;
				i2++;
			} else if (i2 == 0) {  // 条件也可写作next[i2] == -1

				// 相当于str1 i1位置的字符 与 str2的首字符进行对比
				// str2中比对的位置已经无法往前跳， 让主串指向的位置往下移动一个
				i1++;
				// 这里解决了两个场景 一开始就没匹配上自动下一位 以及 匹配上了一部分 后续没匹配上自动下一位、

			} else { // i2可以继续往前跳
				i2 = next[i2]; //str1的i1位置固定不动，str2的 i2 位置往前跳
			}
		}

		// i1越界 或 i2越界
		// i2越界代表i1某个开头一定匹配出str2。  =》  i1-i2是匹配的开头位置
		// i1越界代表i1没有一个开头能匹配出str2
		return i2 == str2.length ? i1 - i2 : -1;
	}

	// 传入一个str2
	public static int[] getNextArray(char[] ms) {
		// 长度为1的时候，只有0位置的信息，人为规定为-1
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		// 长度到了2及2以上，人为规定0位置为-1,1位置为0
		int[] next = new int[ms.length];
		next[0] = -1;
		next[1] = 0;

		int i = 2; // next数组的位置
		int cn = 0; // ①用cn位置的字符与i-1位置的字符进行比较。   ② ！！！cn同时也代表当前使用的next数组的信息
		while (i < next.length) {
			if (ms[i - 1] == ms[cn]) { // 跳出来了
				next[i++] = ++cn;

				/*
				next[i] = cn+1;
				i++; // 表示下次要去求i+1位置的next数组了
				cn++; // 因为下一次要使用到cn++，保证代码的连续性
				 */
			} else if (cn > 0) { // 当跳到cn位置的字符，和i-1位置上的字符对不上，cn要往前跳
				cn = next[cn];
			} else { // 没办法往前跳了
				next[i++] = 0;
			}
		}
		return next;
	}

	public static void main(String[] args) {
		String str = "abcabcababaccc";
		String match = "ababa";
		System.out.println(getIndexOf(str, match));


	}

}
